package com.base.dp;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LongestSubsequence {
    public static void main(String[] args) {
        LongestSubsequence longestSubsequence = new LongestSubsequence();
        System.out.println(longestSubsequence.longestSubsequence(new int[]{1,5,7,8,5,3,4,2,1}, -2));
    }

    /**
     * 数组长度过长的情况下，算法超时
     * @param arr
     * @param difference
     * @return
     */
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(arr[i] - arr[j] == difference){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            maxLen = Math.max(dp[i],maxLen);
        }
        return maxLen;
    }


    public int longestSubsequence2(int[] arr, int difference) {
        //定义一个哈希表，储存以当前元素结尾的等差子序列的长度
        Map<Integer,Integer>  map = new HashMap<>();
        int maxLen = 1;
        for (int i = 0; i < arr.length; i++) {
            //这个链路的前一个值
            int prev = arr[i]- difference;
            if(map.containsKey(prev)){
                //
                map.put(arr[i],map.get(prev)+1);
            }else {
                map.put(arr[i],1);
            }
            maxLen = Math.max(maxLen,map.get(arr[i]));
        }
        return maxLen;
    }

}
